// 给一非空的单词列表，返回前 k 个出现次数最多的单词。

// 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

// 示例 1：

// 输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
// 输出: ["i", "love"]
// 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
//     注意，按字母顺序 "i" 在 "love" 之前。
//  

// 示例 2：

// 输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
// 输出: ["the", "is", "sunny", "day"]
// 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
//     出现次数依次为 4, 3, 2 和 1 次。
//  

// 注意：

// 假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
// 输入的单词均由小写字母组成。
//  

// 扩展练习：

// 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

#include "stdc++.h"

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> record{};
        for (const auto& word : words) {
            ++record[word];
        }
        // 由于map不支持value的sort排序，所以必须将map转换为vector才能进行sort自定义排序
        vector<pair<string, int>> record_vec(record.begin(), record.end());
        auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) {
            if (a.second == b.second) {
                return a.first < b.first;
            } else {
                return a.second > b.second;
            }
        };
        sort(record_vec.begin(), record_vec.end(), cmp);
        vector<string> res(k, "");
        for (int i{0}; i < k; ++i) {
            res[i] = record_vec[i].first;
        }
        return res;
    }
};

/* 堆
*/
class Solution {
public:
    static bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
        if (a.second == b.second) {
            return a.first < b.first;
        }
        return a.second > b.second;
    }
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> dict{};
        for (const auto& word : words) {
            ++dict[word];
        }
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(&cmp)> q(cmp);
        for (const auto& v : dict) {
            if (q.size() == k) {
                if ((q.top().second == v.second && q.top().first > v.first) || q.top().second < v.second) {
                    q.pop();
                    q.emplace(v);
                }
            } else {
                q.emplace(v);
            }
        }
        vector<string> res{};
        while (!q.empty()) {
            res.emplace_back(q.top().first);
            q.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

#include "stdc++.h"

// 哈希表 + 排序
// 时间复杂度：O(MlogM)
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> hash{};
        for (auto& word : words) {
            ++hash[word];
        }
        vector<string> vec{};
        for (auto& p : hash) {
            vec.emplace_back(p.first);
        }
        sort(vec.begin(), vec.end(), [&](const string& a, const string& b) {
            return hash[a] == hash[b] ? a < b : hash[a] > hash[b];
        });
        vec.erase(vec.begin() + k, vec.end());
        return vec;
    }
};

// 优先级队列
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> cnt{};
        for (auto& word : words) {
            ++cnt[word];
        }
        auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp);
        for (auto& it : cnt) {
            que.emplace(it);
            if (que.size() > k) {
                que.pop();
            }
        }
        vector<string> ret(k);
        for (int i{k-1}; i >= 0; --i) {
            ret[i] = que.top().first;
            que.pop();
        }
        return ret;
    }
};